Міністерство науки і освіти України.
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій.
Кафедра ПЗ
Звіт
До лабораторної роботи №3
За курсом «Алгоритми і структури даних».
Тема роботи: Ознайомлення із методами сортування. Алгоритм злиття.
Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із методом сортування злиття. Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема по методу злиття.
1. ТЕОРЕТИЧНІ ВІДОМОСТІ
Сортування злиттям — алгоритм сортування, в основі якого лежить принцип Розділяй та владарюй. В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової.
Підчас сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так до тих пір доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей. Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.
Завдання:
Впорядкувати одновимірний масив методом злиття. Повторити декілька раз з різною кількістю елементів та порівняти час виконання.
Код програми
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<conio.h>
void zluttja (int N[], int mas2[],int n)
{
int d,j,a1,a2,a3,f;
for ( d=1;d<n;d*=2)
{
for( j=0;j<n;j+=d*2)
{
a1=j;
a2=j+d;
a3=j;
while((a1-j<d&&a1<n)||
(a2-j-d<d&&a2<n))
if(a1-j>=d||a1>=n)
mas2[a3++]=N[a2++];
else if(a2-j-d>=d||a2>=n)
mas2[a3++]=N[a1++];
else
mas2[a3++]=(N[a1]<=N[a2])?N[a1++]:N[a2++];
}
for( f=0;f<n;f++)
N[f]=mas2[f];
}
}
int verify(int N[], int d)
{
int k;
for (k=0;k<d-1;k++)
if (N[k]>N[k+1])
return 0;
return 1;
}
void main(void)
{
int N[100000],M[100000];
int i,j,m;
int C[5]={10000,20000,50000,80000,100000};
clock_t start, end;
clrscr();
for (i=0;i<5;i++)
{
for (j=0;j<C[i];j++)
N[j]=rand();
start=clock();
zluttja(N, C[i]);
end=clock();
break;
printf ("%d - %.3f - %s\n", C[i], (end-start)/CLK_TCK, verify(N, C[i]) ? "OK" : "Error");
}
getch();
}
Протокол роботи програми:
Висновок: Час роботи алгоритму по впорядкуванню елементів задовільняє рекурентному співвідношенню:
, де — час на впорядкування половини масиву, — час на злиття цих половинок.
Враховуючи, що , розв'язком співвідношення є .
Крім того, алгоритм потребує для своєї роботи додаткової пам'яті.
Алгоритм не міняє порядок розташування однакових елементів, а отже він є стабільним.
